package LeetCode热题HOT100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class p39组合总和 {
    List< List<Integer> > res=new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        //回溯算法
        Arrays.sort(candidates); //排序后的数组可以进行优化回溯，当前元素==前一个元素，那么就不用对当前元素进行回溯
        List<Integer> path=new ArrayList<>();
        //确定递归函数的参数
        backTrack(candidates,target,path,0,0);
        return res;
    }

    private void backTrack(int[] candidates, int target, List<Integer> path, int sum,int index) {
        //确定递归的终止条件
        if (sum==target) {
            res.add(new ArrayList<>(path));
            return;
        }

        //确定单层递归的逻辑
        for (int i = index; i <candidates.length; i++) {
            if (candidates[index] > target) {
                //剪枝优化
                return;
            }
            if (index>0 && candidates[index]==candidates[index-1]) {
                //剪枝优化
                continue;
            }

            if (sum+candidates[i]>target) {
                return;
            }
            path.add(candidates[i]);

            backTrack(candidates,target,path,sum+candidates[i],i);

            path.remove(path.size()-1);
        }
    }

}
